package com.cwj.lab3.博客需要.欧拉回路问题;

import com.cwj.lab1.LinkStack;
import com.cwj.lab1.myArrayList;
import com.cwj.lab3.博客需要.Graph_matrix_2;
import com.cwj.lab3.博客需要.Graph_table_2;

public class Hierholzer {
    Graph_table_2 graph_table;
    LinkStack<Integer> res = null;
    Graph_matrix_2 graph_matrix;
    boolean isLoop = false;
    int start = 0, end = 0;

    public Hierholzer(Graph_table_2 graph) {
        this.graph_table = graph;
    }

    public Hierholzer(Graph_matrix_2 graph_matrix) {
        this.graph_matrix = graph_matrix;
    }

    public boolean EulerianPathTable() {
        if (this.graph_table == null || this.res != null) {
            return false;
        }
        if(!this.judgeTable_2()){
            return false;
        }
        this.res = new LinkStack<>();
        this.EulerianPathTable(0);
        return true;
    }

    public void EulerianPathTable(int ind) {
        myArrayList<Graph_table_2.Edge> list = this.graph_table.getNodeList().get(ind).getEdgeList();
        for (int i = 0; i < list.size(); i++) {
            EulerianPathTable(list.delLast().getTo());
        }
        this.res.push(ind);
    }

    //其仅仅对于有向图
    public boolean judgeTable_1() {
        myArrayList<Graph_table_2.Node> list = this.graph_table.getNodeList();
        Graph_table_2.Node nn = null;
        for (int i = 0; i < this.graph_table.getV_num(); i++) {
            nn = list.get(i);
            if (nn.getInDegree() != nn.getEdgeList().size()) {
                return false;
            }
        }
        return true;
    }

    public boolean judgeTable_2() {
        myArrayList<Graph_table_2.Node> list = this.graph_table.getNodeList();
        Graph_table_2.Node nn = null;
        int lef = 0;
        int rig = 0;//其中lef代表入度大于出度，rig相反
        int lefNum = 0, rigNum = 0;//对应得结点，如果有多个，那么其值为多少也就无所谓了
        int temp = 0;//入度和出度的差
        for (int i = 0; i < list.size(); i++) {
            nn=list.get(i);
            temp = nn.getInDegree() - nn.getEdgeList().size();
            if (temp != 0) {
                if (temp == 1) {
                    lef += 1;
                    lefNum = i;
                } else if (temp == -1) {
                    rig += 1;
                    rigNum = i;
                } else {
                    return false;
                }
            }
        }
        if (lef == 1 && rig == 1) {
            this.start = lefNum;
            this.end = rigNum;
        } else if (lef == 0 && rig == 0) {
            this.isLoop = true;
        } else {
            return false;
        }
        return true;
    }

    public LinkStack<Integer> getRes() {
        return res;
    }
    public void show(){
        if(res!=null){
            res.show();
        }
    }

    public static void main(String[] args) {
        String path="src/src/com/cwj/lab3/博客需要/欧拉回路问题/有向欧拉图2";
        Graph_table_2 table_2=new Graph_table_2();
        table_2.init_undirect(path,false);
        Hierholzer h=new Hierholzer(table_2);
        h.EulerianPathTable();
        h.show();
    }
}
